package com.banmao.CarlCamp.Day08;

import com.alibaba.fastjson.JSON;

/**
 *  前缀表第一种形式
 */
public class KMP_1 {

    private static int[] getNext(char[] needleChars) {
        // 生成 next 数组
        int[] next = new int[needleChars.length];
        // 1. 初始化
        // j 指向前缀的尾字符
        int j = 0;
        next[0] = j;
        // i 指向后缀的尾字符，从 1 开始
        for (int i = 1; i < needleChars.length; i++) {
            // 2. 处理前后缀不相同的情况
            while (j > 0 && needleChars[i] != needleChars[j]) {
                j = next[j - 1];
            }
            // 3. 处理前后缀相同的情况
            if (needleChars[i] == needleChars[j]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    public static int strStr(String haystack, String needle) {

        int[] next = getNext(needle.toCharArray());

        // i为文本串指针，j为模式串指针
        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return i - j + 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {

        System.out.println(JSON.toJSONString(getNext("leeto".toCharArray())));

        int res = strStr("leetcode", "leeto");
        System.out.println(res);

    }

}
